Page printers, such as laser printers, receive data in page description language form before starting the printing process. With a page description language a page is represented using graphics, text, and images that can be specified to be located anywhere on the page, and in any order, using successive commands of the language. The page description language commands reflect the way the page is composed. However, before printing, the received data must be rasterized so the print mechanism ("print engine") in the printer can print the page while moving the paper uniformly in one direction, usually top to bottom.
Rasterization is the process of converting data that represents a page or portion of a page into a series of individual dots or pixels across the printed page to form a raster scanline, producing successive scanlines one after another down the page. The complete set of scanlines for a page is the raster data for the page. Rasterization is performed in the page printer by a raster generator.
Many page printers rasterize and store the entire raster data for a page before starting to send data to the print engine of the printer. The print engine must run at a predetermined speed. Therefore precomputing the entire page of raster data ensures that each raster scanline is ready to send when needed by the print engine.
To store the raster data for an entire page may require substantial memory. Laser printers have commonly printed about 80 square inches of graphic information on a page at a resolution of 300 dots per inch, both horizontally and vertically. With one bit indicating each dot to be printed or left unprinted, over 875K bytes (one byte equals eight bits) are required to store the raster data for an entire page. To increase the printer speed, a second page of raster data may be computed and stored in additional memory as the raster data for the first page is being sent incrementally to the print engine. Having a second page doubles the memory requirements. New printer technology is enabling 600.times.600 dot (or pixel) resolution continuous tone color printing which may require 24 bits per pixel or more. If full-page storage is used to meet high resolution color requirements, over 80 million bytes of memory per page is required; 160 million bytes of memory are thus required for storing two pages. This is expensive, even relative to the cost of a high-performance color printer.
For low-end printers the memory requirements are less, but the portion of the cost of the memory relative to other printer costs is higher. To provide users with improved printers at lower cost, memory requirements must be reduced.
Several methods have been employed to reduce printer memory requirements while minimizing "printer overrun" errors. A printer overrun error occurs when rasterization does not keep up with the predetermined speed of the print engine. A printer overrun prevents printing the remainder of the page. One method (referenced by Cuzzo, et. al., U.S. Pat. No. 5,129,049) is to store the second page in a format that is more compact than a raster image, so the memory required for it is less than that required for the first full page raster image. The second page could be stored in its original page description language commands, but doing so would not yield the advantage of overlapping the processing time for rasterizing the second page while the first page is being printed. Instead, the page description language commands for the second page are converted on input to an intermediate representation called a "display list." A display list is a sequence of display list commands. Display list commands are relatively simple drawing commands that are faster to rasterize than the original page description language commands. The display list page representation is more compact than a full page of raster data.
Display list commands for the page can be sorted by their position on the page as they are created. By sorting, the display list commands for a page can be separated into multiple sublists. Each sublist is localized for a particular area of the page. This results in display list commands being localized for each area, which leads to another method of saving memory described below.
Rather than rasterize the entire display list for a page before printing, the page is divided into contiguous horizontal strips, and only some of the strips are rasterized before the start of the printing process. All the information for a given strip is contained in the display list commands for that strip. Others are rasterized after printing has started but before they are required by the print engine. By measuring or estimating the rasterization times and keeping track of the running total, some strips may be allowed to take longer to rasterize than others of the same size, so long as the cumulative time stays ahead of the print engine. This is described in the Cuzzo, et al. patent referenced above and incorporated herein by reference. If the rasterization time for rasterization-on-the fly is too large, then one or more strips may be completely pre-rasterized. This approach ensures that the printing process will never fail due to running out of rasterization time, avoiding printer overruns.
In the art, rasterization time estimates are often used rather than performing the rasterization and measuring the actual time required. The actual rasterization Lime may be measured without storing the raster data that results from the process. Good estimates are obtained from formulas based on the parameters that drive the rasterization process. Time estimates must take into account possible processor interruptions for handling unrelated tasks such as communications.
While avoiding printer overruns and minimizing average memory requirements, prior art methods still are subject to running out of memory for difficult cases. In the extreme case of a complex page where each strip requires prerasterization, the printer requires as much memory as a printer that employs no memory-saving technique. Even short of this extreme, minimizing the number of cases that fail requires increasing the amount of available memory.
It is therefore an object of this invention to provide an improved method and system for minimizing the memory requirements for page printers.
It is another object of this invention to provide an improved method and system for preventing loss of printed output for complex pages printed on page printers having limited memory.